package 剑指Offer65.不用加减乘除做加法;

/**        非进位   有进位
 * 0   0     0        0
 * 0   1     1        0
 * 1   0     1        0
 * 1   1     0        1
 *         异或       与（要左移以为）
 * 因此
 *      按位n=a^b
 *      进位c=a&b<<1  计算当前位的进位，然后左移就是进位的结果
 *      结果res=n+c
 *
 * 最终算法：
 *      每次把进位赋值给b,按位赋值给a
 *      while(b!=0) 进位b=0退出循环
 *      最终c=a^b     c记录按位和
 *          b=c&b<<1  b记录进位的值
 *          a=c
 * -8  的补码  11111000
 *
 * 时间：O（1） 最坏32次递归
 * 空间：O(1)
 */
class Solution2 {
    // 把非进位复制给a,把进位赋值给b,递归直到b=0
    public int add(int a, int b) {
        int c=0;
        while (b!=0){ // 如果进位为0那么就可以退出
            c=a^b;    // c 记录按位和
            b=(a&b)<<1; // b记录进位和
            a=c;
        }
        return a;
    }
}